package com.jyl.dp;

/**
 * 动态规划最终版本
 * 时间复杂度：O(n)
 * 空间复杂度：O(1)
 * @ClassName DPFinalVersion
 * @Author admin
 * @Date 2024/6/15
 */
public class DPFinalVersion {

    public static void main(String[] args) {
        System.out.println(fib(100));
    }

    private static long fib(int n) {
        long fnSub2 = 0;  // f(n-2)
        long fnSub1 = 1;  // f(n-1)

        if (n == 0) {
            return 0;
        }

        if (n == 1) {
            return  1;
        }

        for (int i = 2; i <= n ; i++) {
            long result = fnSub2 + fnSub1;
            // 更新变量值
            fnSub2 = fnSub1;
            fnSub1 = result;
        }
        return fnSub1;
    }

}
